package Demo1;

public class Sort {
    public int[] insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {

            int j = i - 1;
            int tmp = arr[i];

            for (; j >= 0 ; j--) {
                if (arr[j] > tmp){
                    arr[j + 1] = arr[j];
                }else{
                    break;
                }
            }

            arr[j + 1] = tmp;
        }

        return arr;
    }


    private void oneShell(int[] arr, int gap){
        for (int i = gap; i < arr.length; i++) {
            int j = i - gap;
            int tmp = arr[i];
            for (; j >= gap; i -= gap){
                if (arr[j] > tmp){
                    arr[j + gap] = arr[j];
                }else{
                    break;
                }
            }

            arr[j + gap] = tmp;
        }
    }

    public int[] shellSort(int[] arr){
        int gap = arr.length;
        while (gap > 1){
            gap /= 2;
            oneShell(arr, gap);
        }

        return arr;
    }
}


class Main3{
    public static void main(String[] args) {
        Sort test3 = new Sort();
        //int[]ret = test3.shellSort(new int[]{5,7,2,3,11,8});
        int[]ret = test3.insertSort(new int[]{5,7,2,3,11,8});

        for (int s : ret){
            System.out.print(s + " ");
        }
    }
}